//https://leetcode.cn/problems/reverse-pairs/description/

class Solution {
    int temp[50010];
public:
    int reversePairs(vector<int>& nums) {
        return mergesort(nums, 0, nums.size() - 1);

    }

    int mergesort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;

        //先找到中间值
        int mid = (l + r) >> 1;
        //统计左右区间的翻转对
        int ret = 0;
        ret += mergesort(nums, l, mid);
        ret += mergesort(nums, mid + 1, r);

        //在合并前从左右区间各选数构成翻转对
        int cur1 = l, end1 = mid, cur2 = mid + 1, end2 = r, i = 0;
        while (cur2 <= end2)  //升序
        {
            while (cur1 <= end1 && nums[cur2] >= nums[cur1] / 2.0) cur1++;
            if (cur1 > end1)
                break;
            //统计翻转对
            ret += end1 - cur1 + 1;

            cur2++;
        }

        cur1 = l;
        cur2 = mid + 1;
        //合并有序数组
        while (cur1 <= end1 && cur2 <= end2)
            temp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= end1)
            temp[i++] = nums[cur1++];
        while (cur2 <= end2)
            temp[i++] = nums[cur2++];

        for (int i = l; i <= r; i++)
        {
            nums[i] = temp[i - l];
        }

        return ret;
    }
};